home *** CD-ROM | disk | FTP | other *** search
/ Technotools / Technotools (Chestnut CD-ROM)(1993).ISO / lang_c / bmg / bmg.c next >
Text File  |  1986-08-29  |  4KB  |  162 lines
  1. /*
  2.  *    bmg.c ->    Boyer-Moore-Gosper search routines
  3.  *
  4.  * Adapted from:
  5.  *   Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  6.  *   original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  7.  *   experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  8.  *   practical value.  However, to improve for worst case input, integrating
  9.  *   the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  10.  *   February 1986) deserves consideration.
  11.  *
  12.  *   James A. Woods                    Copyright (c) 1986
  13.  *   NASA Ames Research Center
  14.  *
  15.  * 29 April 1986    Jeff Mogul    Stanford
  16.  *    Adapted as a set of subroutines for use by a program. No
  17.  *    regular-expression support.
  18.  *
  19.  * 29 August 1986    Frank Whaley    Beyond Words
  20.  *    Trimmed for speed and other dirty tricks.
  21.  */
  22.  
  23. #include <ctype.h>
  24. #include <string.h>
  25. #include "bmg.h"
  26.  
  27. /*  forward declarations  */
  28. static int strncmpi(unsigned char *, unsigned char *, int);
  29. static void lower(char *);
  30.  
  31.  
  32. /*
  33.  *    bmgCompile() ->    compile Boyer-Moore delta table
  34.  *
  35.  *    bmgCompile() compiles the delta table for the given search string, and
  36.  *     initializes the search argument structure.  This structure must be
  37.  *     passed to the bmgSearch() function described below.
  38.  */
  39. void bmgCompile(pat, arg, ignore)
  40.     char    *pat;        /*  the pattern        */
  41.     bmgARG    *arg;        /*  argument data    */
  42.     int    ignore;        /*  TRUE to ignore case    */
  43.     {
  44.     int    i,        /*  general ctr        */
  45.         patlen;        /*  pattern length    */
  46.  
  47.     patlen = strlen(pat);
  48.  
  49. #ifdef    CHECKS
  50.     if (patlen > bmgMAXPAT)
  51.         {
  52.         fprintf(stderr, "bmgCompile: pattern length exceeds %d\n",
  53.             bmgMAXPAT);
  54.         pat[bmgMAXPAT] = 0;    /*  truncate  */
  55.         }
  56. #endif
  57.  
  58.     strcpy(arg->pat, pat);
  59.     if (arg->ignore = ignore)
  60.         lower(arg->pat);
  61.  
  62.     memset(arg->delta, patlen, 256);
  63.  
  64.     for (i = 0; i < patlen; ++i)
  65.         arg->delta[((unsigned char *)pat)[i]] = patlen - i - 1;
  66.  
  67.     if (ignore)    /*  tweak upper case if ignore on  */
  68.         for (i = 0; i < patlen; ++i)
  69.             arg->delta[toupper(((unsigned char *)pat)[i])] = patlen - i - 1;
  70.     }
  71.  
  72.  
  73. /*
  74.  *    bmgSearch() ->    scan for match
  75.  *
  76.  *    bmgSearch() performs a Boyer-Moore-Gosper search of the given buffer
  77.  *     for the string described by the given search argument structure.  The
  78.  *     match action function "action" will be called for each match found.
  79.  *     This function should return non-zero to continue searching, or 0 to
  80.  *     terminate the search.  bmgSearch() returns the total number of
  81.  *     matches found.
  82.  */
  83. int bmgSearch(buffer, buflen, arg, action)
  84.     char    *buffer;    /*  buffer to search        */
  85.     int    buflen;        /*  length of buffer        */
  86.     bmgARG    *arg;        /*  search argument        */
  87.     int    (*action)();    /*  action function        */
  88.     {
  89.     char    *s;        /*  temp ptr for comparisons    */
  90.     int    inc,        /*  position increment        */
  91.         k,        /*  current buffer index    */
  92.         nhits,        /*  match ctr            */
  93.         patlen;        /*  pattern length        */
  94.  
  95.     nhits = 0;
  96.     k = (patlen = strlen(arg->pat)) - 1;
  97.  
  98.     for (;;)
  99.         {
  100.         /*
  101.          *    the following (unsigned char *) type casts save a
  102.          *     few clocks by freeing us from some XCHGs
  103.          */
  104.         while ((inc = arg->delta[((unsigned char *)buffer)[k]]) &&
  105.             ((k += inc) < buflen))
  106.             ;
  107.         if (k >= buflen)
  108.             break;
  109.     
  110.         s = buffer + (k++ - (patlen - 1));
  111.         if (!(arg->ignore ? strncmpi(s, arg->pat, patlen) : strncmp(s, arg->pat, patlen)))
  112.             {
  113.             ++nhits;
  114.             if (!(*action)(buffer, s - buffer))
  115.                 return (nhits);
  116.             }
  117.         }
  118.  
  119.     return (nhits);
  120.     }
  121.  
  122. /*****************************************************************************/
  123. /*****************************  local functions  *****************************/
  124. /*****************************************************************************/
  125.  
  126. /*
  127.  *    lower() ->    lower case a string
  128.  */
  129. static void lower(s)
  130.     char    *s;
  131.     {
  132.     while (*s)
  133.         {
  134.         *s = tolower(*s);
  135.         ++s;
  136.         }
  137.     }
  138.  
  139.  
  140. /*
  141.  *    strncmpi() ->    strncmp(), ignore case
  142.  */
  143. static int strncmpi(s, t, n)
  144.     unsigned char    *s,
  145.             *t;
  146.     int        n;
  147.     {
  148.     for (; n-- && (tolower(*s) == tolower(*t)); ++t)
  149.         if (!*s++)
  150.             return (0);    /* equal */
  151.  
  152.     if (n < 0)        /* maximum hit */
  153.         return (0);        /* equal */
  154.  
  155.     return ((tolower(*s) > tolower(*t)) ? 1 : (-1));    /* not equal */
  156.     }
  157.  
  158.  
  159. /*
  160.  *    END of bmg.c
  161.  */
  162.